home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource4 / 290_01 / dfa.c < prev    next >
C/C++ Source or Header  |  1990-05-14  |  13KB  |  479 lines
  1. /* dfa - DFA construction routines */
  2.  
  3. /*
  4.  * Copyright (c) 1987, the University of California
  5.  * 
  6.  * The United States Government has rights in this work pursuant to
  7.  * contract no. DE-AC03-76SF00098 between the United States Department of
  8.  * Energy and the University of California.
  9.  * 
  10.  * This program may be redistributed.  Enhancements and derivative works
  11.  * may be created provided the new works, if made available to the general
  12.  * public, are made available for use by anyone.
  13.  */
  14.  
  15. #include "flexdef.h"
  16. #include "dfa.h"
  17. #include "misc.h"
  18. #include "ecs.h"
  19.  
  20. /* epsclosure - construct the epsilon closure of a set of ndfa states
  21.  *
  22.  * synopsis
  23.  *    int t[current_max_dfa_size], numstates, accset[accnum + 1], nacc;
  24.  *    int hashval;
  25.  *    int *epsclosure();
  26.  *    t = epsclosure( t, &numstates, accset, &nacc, &hashval );
  27.  *
  28.  * NOTES
  29.  *    the epsilon closure is the set of all states reachable by an arbitrary
  30.  *  number of epsilon transitions which themselves do not have epsilon
  31.  *  transitions going out, unioned with the set of states which have non-null
  32.  *  accepting numbers.  t is an array of size numstates of nfa state numbers.
  33.  *  Upon return, t holds the epsilon closure and numstates is updated.  accset
  34.  *  holds a list of the accepting numbers, and the size of accset is given
  35.  *  by nacc.  t may be subjected to reallocation if it is not large enough
  36.  *  to hold the epsilon closure.
  37.  *
  38.  *    hashval is the hash value for the dfa corresponding to the state set
  39.  */
  40.  
  41. int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
  42. int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
  43.  
  44. {
  45.     register int stkpos, ns, tsp;
  46.     int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
  47.     int stkend, nstate;
  48.     static int did_stk_init = false, *stk;
  49.  
  50. #define MARK_STATE(state) \
  51.         trans1[state] = trans1[state] - MARKER_DIFFERENCE;
  52.  
  53. #define IS_MARKED(state) (trans1[state] < 0)
  54.  
  55. #define UNMARK_STATE(state) \
  56.         trans1[state] = trans1[state] + MARKER_DIFFERENCE;
  57.  
  58. #define CHECK_ACCEPT(state) \
  59.         { \
  60.         nfaccnum = accptnum[state]; \
  61.         if ( nfaccnum != NIL ) \
  62.             accset[++nacc] = nfaccnum; \
  63.         }
  64.  
  65.     #define DO_REALLOCATION \
  66.         { \
  67.         current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \
  68.         ++num_reallocs; \
  69.         t = reallocate_integer_array( t, current_max_dfa_size ); \
  70.         stk = reallocate_integer_array( stk, current_max_dfa_size ); \
  71.         } \
  72.  
  73. #define PUT_ON_STACK(state) \
  74.         { \
  75.         if ( ++stkend >= current_max_dfa_size ) \
  76.             DO_REALLOCATION \
  77.         stk[stkend] = state; \
  78.         MARK_STATE(state) \
  79.         }
  80.  
  81. #define ADD_STATE(state) \
  82.         { \
  83.         if ( ++numstates >= current_max_dfa_size ) \
  84.             DO_REALLOCATION \
  85.         t[numstates] = state; \
  86.         hashval = hashval + state; \
  87.         }
  88.  
  89. #define STACK_STATE(state) \
  90.         { \
  91.         PUT_ON_STACK(state) \
  92.         CHECK_ACCEPT(state) \
  93.         if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \
  94.             ADD_STATE(state) \
  95.         }
  96.  
  97.     if ( ! did_stk_init )
  98.     {
  99.         stk = allocate_integer_array( current_max_dfa_size );
  100.         did_stk_init = true;
  101.     }
  102.  
  103.     nacc = stkend = hashval = 0;
  104.  
  105.     for ( nstate = 1; nstate <= numstates; ++nstate )
  106.     {
  107.         ns = t[nstate];
  108.  
  109.         /* the state could be marked if we've already pushed it onto
  110.          * the stack
  111.          */
  112.         if ( ! IS_MARKED(ns) )
  113.             PUT_ON_STACK(ns)
  114.  
  115.               CHECK_ACCEPT(ns)
  116.               hashval = hashval + ns;
  117.     }
  118.  
  119.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  120.     {
  121.         ns = stk[stkpos];
  122.         transsym = transchar[ns];
  123.  
  124.         if ( transsym == SYM_EPSILON )
  125.         {
  126.             tsp = trans1[ns] + MARKER_DIFFERENCE;
  127.  
  128.             if ( tsp != NO_TRANSITION )
  129.             {
  130.                 if ( ! IS_MARKED(tsp) )
  131.                     STACK_STATE(tsp)
  132.  
  133.                       tsp = trans2[ns];
  134.  
  135.                 if ( tsp != NO_TRANSITION )
  136.                     if ( ! IS_MARKED(tsp) )
  137.                         STACK_STATE(tsp)
  138.             }
  139.         }
  140.     }
  141.  
  142.     /* clear out "visit" markers */
  143.  
  144.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  145.     {
  146.         if ( IS_MARKED(stk[stkpos]) )
  147.         {
  148.             UNMARK_STATE(stk[stkpos])
  149.         }
  150.         else
  151.             flexfatal( "consistency check failed in epsclosure()" );
  152.     }
  153.  
  154.     *ns_addr = numstates;
  155.     *hv_addr = hashval;
  156.     *nacc_addr = nacc;
  157.  
  158.     return ( t );
  159. }
  160.  
  161.  
  162.  
  163. /* increase_max_dfas - increase the maximum number of DFAs */
  164.  
  165. void increase_max_dfas()
  166.  
  167. {
  168.     int old_max = current_max_dfas;
  169.  
  170.     current_max_dfas += MAX_DFAS_INCREMENT;
  171.  
  172.     ++num_reallocs;
  173.  
  174.     base = reallocate_integer_array( base, current_max_dfas );
  175.     def = reallocate_integer_array( def, current_max_dfas );
  176.     dfasiz = reallocate_integer_array( dfasiz, current_max_dfas );
  177.     accsiz = reallocate_integer_array( accsiz, current_max_dfas );
  178.     dhash = reallocate_integer_array( dhash, current_max_dfas );
  179.     todo = reallocate_integer_array( todo, current_max_dfas );
  180.     dss = reallocate_intptr_array( dss, current_max_dfas );
  181.     dfaacc = reallocate_dfaacc_union( dfaacc, current_max_dfas );
  182.  
  183.     /* fix up todo queue */
  184.     if ( todo_next < todo_head )
  185.     { /* queue was wrapped around the end */
  186.         register int i;
  187.  
  188.         for ( i = 0; i < todo_next; ++i )
  189.             todo[old_max + i] = todo[i];
  190.  
  191.         todo_next += old_max;
  192.     }
  193. }
  194.  
  195.  
  196. /* snstods - converts a set of ndfa states into a dfa state
  197.  *
  198.  * synopsis
  199.  *    int sns[numstates], numstates, newds, accset[accnum + 1], nacc, hashval;
  200.  *    int snstods();
  201.  *    is_new_state = snstods( sns, numstates, accset, nacc, hashval, &newds );
  202.  *
  203.  * on return, the dfa state number is in newds.
  204.  */
  205.  
  206. int snstods( sns, numstates, accset, nacc, hashval, newds_addr )
  207. int sns[], numstates, accset[], nacc, hashval, *newds_addr;
  208.  
  209. {
  210.     int didsort = 0;
  211.     register int i, j;
  212.     int newds, *oldsns;
  213.  
  214.  
  215.     for ( i = 1; i <= lastdfa; ++i )
  216.         if ( hashval == dhash[i] )
  217.         {
  218.             if ( numstates == dfasiz[i] )
  219.             {
  220.                 oldsns = dss[i];
  221.  
  222.                 if ( ! didsort )
  223.                 {
  224.                     /* we sort the states in sns so we can compare it to
  225.                      * oldsns quickly.  we use bubble because there probably
  226.                      * aren't very many states
  227.                      */
  228.                     bubble( sns, numstates );
  229.                     didsort = 1;
  230.                 }
  231.  
  232.                 for ( j = 1; j <= numstates; ++j )
  233.                     if ( sns[j] != oldsns[j] )
  234.                         break;
  235.  
  236.                 if ( j > numstates )
  237.                 {
  238.                     ++dfaeql;
  239.                     *newds_addr = i;
  240.                     return ( 0 );
  241.                 }
  242.  
  243.                 ++hshcol;
  244.             }
  245.  
  246.             else
  247.                 ++hshsave;
  248.         }
  249.  
  250.     /* make a new dfa */
  251.  
  252.     if ( ++lastdfa >= current_max_dfas )
  253.         increase_max_dfas();
  254.  
  255.     newds = lastdfa;
  256.  
  257.     if ( ! (dss[newds] = (int *) malloc( (unsigned) ((numstates + 1) * sizeof( int
  258.       )) )) )
  259.         flexfatal( "dynamic memory failure in snstods()" );
  260.  
  261.     /* if we haven't already sorted the states in sns, we do so now, so that
  262.      * future comparisons with it can be made quickly
  263.      */
  264.  
  265.     if ( ! didsort )
  266.         bubble( sns, numstates );
  267.  
  268.     for ( i = 1; i <= numstates; ++i )
  269.         dss[newds][i] = sns[i];
  270.  
  271.     dfasiz[newds] = numstates;
  272.     dhash[newds] = hashval;
  273.  
  274.     if ( nacc == 0 )
  275.     {
  276.         dfaacc[newds].dfaacc_state = 0;
  277.         accsiz[newds] = 0;
  278.     }
  279.  
  280.     else if ( reject )
  281.     {
  282.         /* we sort the accepting set in increasing order so the disambiguating
  283.          * rule that the first rule listed is considered match in the event of
  284.          * ties will work.  We use a bubble sort since the list is probably
  285.          * quite small.
  286.          */
  287.  
  288.         bubble( accset, nacc );
  289.  
  290.         dfaacc[newds].dfaacc_state =
  291.           (int *) malloc( (unsigned) ((nacc + 1) * sizeof( int )) );
  292.  
  293.         if ( ! dfaacc[newds].dfaacc_state )
  294.             flexfatal( "dynamic memory failure in snstods()" );
  295.  
  296.         /* save the accepting set for later */
  297.         for ( i = 1; i <= nacc; ++i )
  298.             dfaacc[newds].dfaacc_set[i] = accset[i];
  299.  
  300.         accsiz[newds] = nacc;
  301.     }
  302.  
  303.     else
  304.     { /* find lowest numbered rule so the disambiguating rule will work */
  305.         j = accnum + 1;
  306.  
  307.         for ( i = 1; i <= nacc; ++i )
  308.             if ( accset[i] < j )
  309.                 j = accset[i];
  310.  
  311.         dfaacc[newds].dfaacc_state = j;
  312.     }
  313.  
  314.     *newds_addr = newds;
  315.  
  316.     return ( 1 );
  317. }
  318.  
  319.  
  320. /* symfollowset - follow the symbol transitions one step
  321.  *
  322.  * synopsis
  323.  *    int ds[current_max_dfa_size], dsize, transsym;
  324.  *    int nset[current_max_dfa_size], numstates;
  325.  *    numstates = symfollowset( ds, dsize, transsym, nset );
  326.  */
  327.  
  328. int symfollowset( ds, dsize, transsym, nset )
  329. int ds[], dsize, transsym, nset[];
  330.  
  331. {
  332.     int ns, tsp, sym, i, j, lenccl, ch, numstates;
  333.     int ccllist;
  334.  
  335.     numstates = 0;
  336.  
  337.     for ( i = 1; i <= dsize; ++i )
  338.     { /* for each nfa state ns in the state set of ds */
  339.         ns = ds[i];
  340.         sym = transchar[ns];
  341.         tsp = trans1[ns];
  342.  
  343.         if ( sym < 0 )
  344.         { /* it's a character class */
  345.             sym = -sym;
  346.             ccllist = cclmap[sym];
  347.             lenccl = ccllen[sym];
  348.  
  349.             if ( cclng[sym] )
  350.             {
  351.                 for ( j = 0; j < lenccl; ++j )
  352.                 { /* loop through negated character class */
  353.                     ch = ccltbl[ccllist + j];
  354.  
  355.                     if ( ch > transsym )
  356.                         break;  /* transsym isn't in negated ccl */
  357.  
  358.                     else if ( ch == transsym )
  359.                         /* next 2 */ goto bottom;
  360.                 }
  361.  
  362.                 /* didn't find transsym in ccl */
  363.                 nset[++numstates] = tsp;
  364.             }
  365.  
  366.             else
  367.                 for ( j = 0; j < lenccl; ++j )
  368.                 {
  369.                     ch = ccltbl[ccllist + j];
  370.  
  371.                     if ( ch > transsym )
  372.                         break;
  373.  
  374.                     else if ( ch == transsym )
  375.                     {
  376.                         nset[++numstates] = tsp;
  377.                         break;
  378.                     }
  379.                 }
  380.         }
  381.  
  382.         else if ( sym >= 'A' && sym <= 'Z' && caseins )
  383.             flexfatal( "consistency check failed in symfollowset" );
  384.  
  385.         else if ( sym == SYM_EPSILON )
  386.         { /* do nothing */
  387.         }
  388.  
  389.         else if ( ecgroup[sym] == transsym )
  390.             nset[++numstates] = tsp;
  391.  
  392. bottom:
  393.         ;
  394.     }
  395.  
  396.     return ( numstates );
  397. }
  398.  
  399.  
  400. /* sympartition - partition characters with same out-transitions
  401.  *
  402.  * synopsis
  403.  *    integer ds[current_max_dfa_size], numstates, duplist[numecs];
  404.  *    symlist[numecs];
  405.  *    sympartition( ds, numstates, symlist, duplist );
  406.  */
  407.  
  408. void sympartition( ds, numstates, symlist, duplist )
  409. int ds[], numstates, duplist[];
  410. int symlist[];
  411.  
  412. {
  413.     int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich;
  414.  
  415.     /* partitioning is done by creating equivalence classes for those
  416.      * characters which have out-transitions from the given state.  Thus
  417.      * we are really creating equivalence classes of equivalence classes.
  418.      */
  419.  
  420.     for ( i = 1; i <= numecs; ++i )
  421.     { /* initialize equivalence class list */
  422.         duplist[i] = i - 1;
  423.         dupfwd[i] = i + 1;
  424.     }
  425.  
  426.     duplist[1] = NIL;
  427.     dupfwd[numecs] = NIL;
  428.  
  429.     for ( i = 1; i <= numstates; ++i )
  430.     {
  431.         ns = ds[i];
  432.         tch = transchar[ns];
  433.  
  434.         if ( tch != SYM_EPSILON )
  435.         {
  436.             if ( tch < -lastccl || tch > CSIZE )
  437.                 flexfatal( "bad transition character detected in sympartition()" );
  438.  
  439.             if ( tch > 0 )
  440.             { /* character transition */
  441.                 mkechar( ecgroup[tch], dupfwd, duplist );
  442.                 symlist[ecgroup[tch]] = 1;
  443.             }
  444.  
  445.             else
  446.             { /* character class */
  447.                 tch = -tch;
  448.  
  449.                 lenccl = ccllen[tch];
  450.                 cclp = cclmap[tch];
  451.                 mkeccl( ccltbl + cclp, lenccl, dupfwd, duplist, numecs );
  452.  
  453.                 if ( cclng[tch] )
  454.                 {
  455.                     j = 0;
  456.  
  457.                     for ( k = 0; k < lenccl; ++k )
  458.                     {
  459.                         ich = ccltbl[cclp + k];
  460.  
  461.                         for ( ++j; j < ich; ++j )
  462.                             symlist[j] = 1;
  463.                     }
  464.  
  465.                     for ( ++j; j <= numecs; ++j )
  466.                         symlist[j] = 1;
  467.                 }
  468.  
  469.                 else
  470.                     for ( k = 0; k < lenccl; ++k )
  471.                     {
  472.                         ich = ccltbl[cclp + k];
  473.                         symlist[ich] = 1;
  474.                     }
  475.             }
  476.         }
  477.     }
  478. }
  479.